%!TEX root = main.tex

\section{Problem Setting}
\label{sec:problem}

Assume a corpus of tables $\mathcal{T}$ extracted from the same site.  Our goal is to build a pipeline for 
stitching tables in $\mathcal{T}$ into a set of union tables. This pipeline consists of three major 
components: the stitchable table identifier, the hidden attribute extractor and the table stitcher.

\smallskip
\noindent
{\bf Stitchable Tables Identifier:} 
To identify a set of stitchable tables from a corpus $\mathcal{T}$, we 
rely on the header $h_T$ of a table $T$~\footnote{$h_T$ is a set of string values that are the column 
names of $T$. In the example shown in Figure \ref{fig:overview}, they are ``Town'', ``School'', ``\# 
Students'' and ``Grades''.}. We define {\em stitchable tables} as follows:

\begin{definition}(Stitchable Tables):
Two tables  $T_1$ and $T_2$ are stitchable if their headers $h_{T_1}$ and $h_{T_2}$ are {\em semantically 
equivalent} regardless of the ordering, $h_{T_1} \equiv h_{T_2}$. Specifically, for all attribute names
$h_{T_1}(i)$ in $h_{T_1}$ there exists one and only one attribute name $h_{T_2}(j)$ in $h_{T_2}$ that has the 
same meaning of $h_{T_2}(i)$ and the reverse also holds. Note that the stitchable property is transitive: if 
$T_1$ and $T_2$ are stitchable and so are $T_2$ and $T_3$, then $T_1$ and $T_3$ are stitchable.
\end{definition}

We can potentially define semantic equivalence based on non-trivial notions such as synonymy, acronyms or 
many other semantic-preserving variations. For simplicity, however, we simply consider semantic equivalence
as two sets of attribute names having exactly the same set of string values. Our stitching techniques are 
orthogonal to stitchable tables identification, thus we leave advanced identifiers for future work. Once 
identified, all stitchable tables are grouped together for stitching. Because of the transitivity nature, 
each table can only belong to one stitchable group.

\smallskip
\noindent
{\bf Hidden Attribute Extractor:} For each stitchable group $G =\{T_1, \cdots, T_n\}$, our goal is to union 
the element tables without creating semantic ambiguities. As mentioned above, two schools from different 
counties could have exactly the same name. Information that can be used to disambiguate those rows are often 
hidden within the table context.  The challenge, however, is that such information is usually presented as 
unstructured natural language context on the page---we need to extract, as precisely and concisely as 
possible, a set of structured hidden attributes $m_T$ from such context to make each table distinguishable 
within the group. The set of hidden attributes $m_T$ is represented as an ordered list of values,
$\{m_1^T, \cdots , m_{M_G}^T\}$, where $M_G$ is the number of hidden attributes for the group. Note that we 
are making the assumption that all tables within the same group have the same set of hidden attributes. If a 
particular attribute is missing from a table, we can simply assign it null for that table.

\smallskip
\noindent
{\bf Table Stitcher:} The final step is to stitch the tables in the same group. For each table $T$ in a group 
$G$, its induced attributes $m_T$ will be appended to each tuple in $T$. The augmented tables are then simply 
concatenated together. Those induced attribute values, however, are often difficult to understand and 
leverage by applications because of the lack of attribute names on the newly created columns. To enrich those hidden attributes, we leverage 
techniques inspired by \cite{venetis2011recovering}, in which we match the values in the cells to a database of {\tt isA} relations~\cite{pasca2008weakly}. If a significant number of values in a column get mapped to a common class in the {\tt isA} database, we use the class name as the attribute name. We discuss the effectiveness of this 
simple approach using empirical results in Section \ref{sec:col-label}.
